#include <cmath>
#include <iostream>
#include <list>
#include <vector>
using namespace std;
//方法一
class Solution
{
public:
    bool check(int hashs[], int hashp[])
    {
        for(int i = 0; i < 26; i++)
        {
            if(hashs[i] != hashp[i])
            {
                return false;
            }
        }
        return true;
    }

    vector<int> findAnagrams(string s, string p)
    {
        int left = 0;
        int right = 0;
        int hashs[26] = {0};
        int hashp[26] = {0};
        int m = p.size();
        vector<int> rv;
        for(auto e : p)
        {
            hashp[e-'a']++;
        }

        while(right < s.size())
        {
            char in = s[right];
            hashs[in-'a']++;
            if(right-left+1 > m)
            {
                char out = s[left++];
                hashs[out-'a']--;
            }
            if(check(hashs, hashp))
            {
                rv.push_back(left);
            }
            right++;
        }
        return rv;
    }
};

//方法二
class Solution2
{
public:
    static vector<int> findAnagrams(string s, string p)
    {
        int left = 0;
        int right = 0;
        int hashs[26] = {0};
        int hashp[26] = {0};
        int m = p.size();
        vector<int> rv;
        for(auto e : p)
        {
            hashp[e-'a']++;
        }
        int count = 0;
        while(right < s.size())
        {
            char in = s[right];
            if(++hashs[in-'a'] <= hashp[in-'a'])
                count++;
            if(right-left+1 > m)
            {
                char out = s[left++];
                if(hashs[out-'a']-- <= hashp[out-'a'])
                    count--;
            }
            if(count == m)
            {
                rv.push_back(left);
            }
            right++;
        }
        return rv;
    }
};
